题面

给出一个 $N\times N(N\le 1000)$ 矩阵，矩阵中自然数 $\in [0,2^{31}-1]$

求，所有子矩阵 AND 与 OR 之和，对 $1,000,000,007 (10^9 + 7)$ 取模

解题思路

二进制拆位+单调栈

分析

对于二进制操作的，一般都想到拆位后处理，拆位后就变成了 $0/1$ 矩阵，处理起来就很方便

因此先拆位，这样问题形式就变成了：求有几个子矩阵 AND 值为 1，OR 值为 1

怎么求子矩阵？

由于 $N$ 的范围在 $1000$，$N\times N$ 就是 $10^6$，猜测可以枚举每个子矩阵的右下角，然后用线性的数据结构维护一下

由于 AND 和 OR 操作的性质，只要有 1 或 0 就可以确定当前的结果

因此可以记录一个在以 $(1,1)$ 为左上角，$(i,j)$ 这个点为右下角的矩阵中，离 $(i,j)$ 较近的 1 和 0 的位置

由于 AND 和 OR 操作本质是一致的，因此以下均只论述 OR 的情况

为什么说是较近？

如图：

1-1

对 $(3,3)$ 来说，较近的点有 $(2,3)$ 和 $(3,1)$，因为如果左上角在 $(3,1)$ 或 $(2,3)$ 的左上方，则 OR 的值定为 1

换句话说，这里的较近点的含义即是会对答案产生影响的点，显然，这些点一定成一条走向为矩阵左下角到右上角的直线，即若 $j$ 的值有序，则 $i$ 值定单调，于是就可以考虑用单调栈维护这些点

如何计算子矩阵的贡献？

既然我们用单调栈维护了这么一个东西，在更新的过程中得出答案

仍以上图为例，我们用 b[j][1] 表示以当前位置为右下角的矩阵中，在第 $j$ 列，1 最大的 $i$ 值

然后单调队列维护的应是随着 $j$ 逐渐增大，$i$ 值逐渐减小的栈

  • 假设我们大家当前做到 $i=3$ ，一开始要把栈清空

    当 $j=1$ 时，$b[1][1]=3$，直接入栈，并加上贡献 res1+=b[j][1]=3

    当 $j=2$ 时，$b[2][1]=1$，仍然直接入栈，并加上贡献 res1+=b[j][1]=1

    当 $j=3$ 时，$b[3][1]=2$，为了维护单调，要把 $1$ 弹出，并加上如图所示区域的贡献 --t1,res1+=(j-v1[t1]-1)*(min(St1[t1],b[j][1])-St1[t1+1])=1，$t1$ 表示栈顶，St1[_] 存的是 b[_][1]，v1[_] 存的是 $j$ 值

1-2

取 min(St1[t1],b[j][1]) 是因为又能会出现如下另外两种情况

1-3

1-4

关注在 $(3,3)$ 时情况，虽然这两种情况有点相似，但是仍需要注意

还有一点就是把栈弹空的情况（如上图 $1-3$ 和 $1-4$），此时要特判，否则取 min(St1[t1],b[j][1]) 的结果为 0

warning

1、记得初始化记录 $i$ 的数组

2、AND 维护的是 0 的单调栈，因此最后计算个数的时候答案应为 i*j-res0

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define p 1000000007
#define N 1003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,f[N][N],b[N][2],res0,res1,l1,l0,M;
int St1[N],St0[N],t0,t1,v0[N],v1[N];
LL c,ans1,ans0;
int main()
{
    rint i,j;n=read();
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            cmax(M,f[i][j]=read());
    for(c=1;c<=M;c<<=1) {
        memset(b,0,sizeof(b));//记得初始化b数组
        for(i=1;i<=n;i++) {
            t0=t1=res1=res0=0;
            for(j=1;j<=n;j++) {
                if(f[i][j]&c) b[j][1]=i;//更新b数组
                else b[j][0]=i;
                res0+=b[j][0],res1+=b[j][1];
                while(t0&&St0[t0]<=b[j][0])//维护单调栈，也可以和if写在一起，但是第一次写挂之后就懒得改了
                    if(--t0) res0+=(j-v0[t0]-1)*(min(St0[t0],b[j][0])-St0[t0+1]);
                    else res0+=(j-1)*(b[j][0]-St0[1]);
                St0[++t0]=b[j][0],v0[t0]=j;
                while(t1&&St1[t1]<=b[j][1])
                    if(--t1) res1+=(j-v1[t1]-1)*(min(St1[t1],b[j][1])-St1[t1+1]);
                    else res1+=(j-1)*(b[j][1]-St1[1]);
                St1[++t1]=b[j][1],v1[t1]=j;
                ans1=(ans1+res1*c)%p,//分开计算贡献
                ans0=(ans0+(i*j-res0)*c)%p;
            }
        }
    }printf("%lld %lld",ans0,ans1);
    return 0;
}

弱化版 Luogu P3400 仓鼠窝

devil.